﻿#pragma once

#include<iostream>

using namespace std;




//1.红黑树基本规则
	//1.1、每个结点不是红⾊就是⿊⾊
	//1.2、根结点是⿊⾊的
	//1.3、如果⼀个结点是红⾊的，则它的两个孩⼦结点必须是⿊⾊的，也就是说任意⼀条路径不会有连续的红⾊结点
	//1.4、对于任意⼀个结点，从该结点到其所有NULL结点的简单路径上，均包含相同数量的⿊⾊结点


//2.代码实现
enum Colour//每个节点只有红色和黑色
{
	RED,
	BLACK
};

template<class K, class V>
struct RBTreeNode//节点
{
	pair<K, V> _kv;
	RBTreeNode* _left;
	RBTreeNode* _right;
	RBTreeNode* _parent;
	Colour _col;

	RBTreeNode(const pair<K,V>& kv)
		:_kv(kv)
		,_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
	{ }
};

template<class K,class V>
class RBTree//树
{
	typedef RBTreeNode<K, V> Node;
public:
	bool Insert(const pair<K, V>& kv)//插入
	{
		//2.1找到插入节点位置
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first > kv.first)//小往左
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_kv.first < kv.first)//大往右
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false;
			}
		}

		//2.2插入，插入的节点颜色一定为红色，不然不符合红黑树基本规则
		cur = new Node(kv);
		cur->_col = RED;
		if (parent->_kv.first > kv.first)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		cur->_parent = parent;

		//2.3插入后的维护，使插入后树仍为红黑树
		//有三种情况需要维护，若父亲为黑，插入后不需要更新维护
		//插入节点c(cur)为红，父亲节点p(parent)为红，那祖父节点g(grandfather)一定为黑(要符合红黑树规则1.3)
		//	对于叔父节点u(uncle)有三种情况，为红为黑和为空，这三种情况都需要更新维护使树为红黑树
		//	为红只需要变色，为黑和为空需要旋转加变色
		while (parent && parent->_col == RED)
		{
			Node* grandfather = parent->_parent;//祖父
			if (grandfather->_left == parent)
			{
				Node* uncle = grandfather->_right;
				if (uncle && uncle->_col == RED)//为红只需变色
				{
					//变色
					grandfather->_col = RED;
					parent->_col = uncle->_col = BLACK;

					//往上处理，祖父变红，由于祖祖父也可能是红色，需要往上继续处理
					cur = grandfather;
					parent = cur->_parent;
				}
				else//为黑为空处理方式类似，旋转加变色，u是黑或空
				{	//至于为什么要让顶点为黑(因为顶点为红，节点为黑也符合红黑树规则)，避免往上继续处理，高效
					//		g黑			  p黑
					//	  p红  u	-> 	c红	g红    我们这里条件是uncle是grandfather右节点
					//	c红					 u     这种只需单旋，具体画图，跟avl树类似
					if (cur == parent->_left)
					{
						RotateR(grandfather);//只需右旋祖父节点
						parent->_col = BLACK;//颜色更新
						grandfather->_col = RED;
					}
					else
					{//		 g黑			   c黑
					 //	  p红	u		->	p红	  g红
					 //	   c红				       u			这种需要双旋，先左旋p，再右旋g
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}

					break;//维护完成，退出循环
				}
			}
			else//grandfather->_right == parent;
			{
				Node* uncle = grandfather->_left;
				if (uncle && uncle->_col == RED)
				{
					grandfather->_col = RED;
					parent->_col = uncle->_col = BLACK;
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					if (cur == parent->_right)
					{
						RotateL(grandfather);
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
		}//while循环

		_root->_col = BLACK;

		return true;
	}//Insert()
	
	void RotateL(Node* parent)//左旋
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		if (subRL)
		{
			subRL->_parent = parent;
		}
		Node* parentParent = parent->_parent;
		subR->_left = parent;
		parent->_parent = subR;

		if (parentParent == nullptr)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (parent == parentParent->_left)
			{
				parentParent->_left = subR;
			}
			else
			{
				parentParent->_right = subR;
			}

			subR->_parent = parentParent;
		}
	}

	void RotateR(Node* parent)//右旋
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
		{
			subLR->_parent = parent;
		}
		Node* parentParent = parent->_parent;
		subL->_right = parent;
		parent->_parent = subL;

		if (parentParent == nullptr)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (parent == parentParent->_left)
			{
				parentParent->_left = subL;
			}
			else
			{
				parentParent->_right = subL;
			}

			subL->_parent = parentParent;
		}
	}

	Node* Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first > key)//小往左找
			{
				cur = cur->_left;
			}
			else if (cur->_kv.first < key)//大往右找
			{
				cur = cur->_right;
			}
			else
			{
				return cur;
			}
		}

		return nullptr;//未找到返回空指针;
	}

	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

	int Height()
	{
		return _Height(_root);
	}

	int Size()
	{
		return _Size(_root);
	}

	bool IsBalance()
	{//1.全红或黑节点
	 //2.根为黑
	 //3.红子必为黑
	 //4.每条路径黑同

		if (_root == nullptr)//空树符合
			return true;

		//规则1必定成立，我们枚举颜色只有红黑
		if (_root->_col == RED)//规则2
			return false;

		Node* cur = _root;
		int refNum = 0;//记录下一条路径黑色节点数量
		while (cur)
		{
			if (cur->_col == BLACK)
				++refNum;
			cur = cur->_left;
		}

		return Check34(_root, 0, refNum);
	}

private:

	bool Check34(Node* root, int blackNum, const int refNum)//
	{//refNum是参照量，检测每条路径上黑色节点数是否相同
		if (root == nullptr)//当root为空，说明递归到底部节点，检测blackNum是否根refNum相同
		{
			if (blackNum != refNum)
			{
				cout << "存在黑色节点数量不相同的路径" << endl;
				return false;
			}
			return true;
		}

		if (root->_col == BLACK)//检测到黑色节点，blackNum++，到root为空，抵达根部，blackNum就是这条路径上黑色节点数量
		{
			++blackNum;
		}

		if (root->_col == RED && root->_parent->_col == RED)//若几点与其父皆为红，则不符合规则3
		{
			cout << "存在红色节点子节点为红色" << endl;
			return false;
		}

		return Check34(root->_left, blackNum, refNum)//递归检查左右
			&& Check34(root->_right, blackNum, refNum);//当
	}

	void _InOrder(Node* root)//中序遍历
	{
		if (root == nullptr)
		{
			return;
		}

		_InOrder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second << endl;
		_InOrder(root->_right);
	}

	int _Height(Node* root)//深度
	{
		if (root == nullptr)
			return 0;
		int leftHeight = _Height(root->_left);
		int RightHeight = _Height(root->_right);
		return leftHeight > RightHeight ? leftHeight + 1 : RightHeight + 1;//哪边大选哪边然后+1
	}

	int _Size(Node* root)//节点个数
	{
		if (root == nullptr)
			return 0;
		return _Size(root->_left) + _Size(root->_right) + 1;
	}

	Node* _root = nullptr;
};


